package com.example.demo.MyTest;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @description:
 * @author: yyc
 * @time: 2021/11/23 19:01
 */
public class SolutionT001 {

    /**
     * 测试
     * @param args
     */
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.val = 1;
        TreeNode left = new TreeNode();
        left.val = 2;
        treeNode.left = left;
        TreeNode ll = new TreeNode();
        ll.val=3;
        treeNode.left.left = ll;
        TreeNode lR = new TreeNode();
        lR.val = 4;
        treeNode.left.right = lR;

        TreeNode right= new TreeNode();
        right.val = 5;
        treeNode.right = right;

        TreeNode Rl = new TreeNode();
        Rl.val=6;
        treeNode.right.left = Rl;
        TreeNode RR = new TreeNode();
        RR.val = 7;
        treeNode.right.right = RR;

        List<Integer> list = new ArrayList<>();
        //前序 根左右
//        System.out.println("前序遍历......");
//        formerSequenceTraversal(treeNode,list);
        //中序 左根右
        System.out.println("中序遍历......");
        midSequenceTraversal(treeNode,list);
        //后序 左右根
        System.out.println("后序遍历......");
        afterSequenceTraversal(treeNode,list);
    }

    static class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;
        //构造函数...
        TreeNode(){}
        TreeNode(int val){this.val=val;}
        TreeNode(int val,TreeNode left,TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    private static void formerSequenceTraversal(TreeNode node, List<Integer> resultList){
        if(node==null){
            return;
        }
        resultList.add(node.val);
        System.out.print(node.val);
        formerSequenceTraversal(node.left,resultList);
        formerSequenceTraversal(node.right,resultList);
    }

    private static void midSequenceTraversal(TreeNode node, List<Integer> resultList){
        if(node==null){
            return;
        }
        midSequenceTraversal(node.left,resultList);
        System.out.print(node.val);
        resultList.add(node.val);
        midSequenceTraversal(node.right,resultList);
    }

    private static void afterSequenceTraversal(TreeNode node, List<Integer> resultList){
        if(node==null){
            return;
        }
        afterSequenceTraversal(node.left,resultList);
        afterSequenceTraversal(node.right,resultList);
        System.out.print(node.val);
        resultList.add(node.val);
    }

    /**
     * 前序遍历 迭代法
     * @param root
     */
    private List<Integer> former(TreeNode root){
        if(root==null){
            return null;
        }

        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();

        while (!stack.isEmpty() || root!=null){
            while(root!=null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        return list;
    }

}
